package com.leetcode.contest;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/11/13 22:44
 */
public class LC5912每一个查询的最大美丽值 {

    public static int[] maximumBeauty(int[][] items, int[] queries) {
        List<Integer> answer = new ArrayList<>();
        Arrays.sort(items, (o1, o2) -> {
            if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]);
            return Integer.compare(o1[1], o2[1]);
        });

        TreeMap<Integer, Integer> priceToBeauty = new TreeMap<>();
        for (int[] item : items) {
            int key = item[0];
            Integer lowerKey = priceToBeauty.lowerKey(key);
            if (lowerKey == null) priceToBeauty.put(item[0], item[1]);
            else {
                //第lowerKey的值进行比较
                int lowerBeauty = priceToBeauty.get(lowerKey);
                priceToBeauty.put(key, Math.max(item[1], lowerBeauty));
            }
        }

        for (int query : queries) {
            if (priceToBeauty.containsKey(query)) {
                answer.add(priceToBeauty.get(query));
            } else {
                Integer lowerKey = priceToBeauty.lowerKey(query);
                if (lowerKey == null) answer.add(0);
                else answer.add(priceToBeauty.get(lowerKey));
            }
        }
        return answer.stream().mapToInt(val -> val).toArray();
    }

    public static void main(String[] args) {
        int[][] items = {{1, 2}, {3, 2}, {2, 4}, {5, 6}, {3, 5}};
        int[] queries = {1, 2, 3, 4, 5, 6};
//        int[][] items = {{10, 1000}};
//        int[] queries = {5};
//        int[][] items = {{10, 5}, {6, 10}};
//        int[] queries = {11};
        System.out.println(Arrays.toString(maximumBeauty(items, queries)));
    }
}
